# ํต ์ ๋ ฌ(Quick Sort)
# Goal
- Quick Sort์ ๋ํด ์ค๋ช ํ ์ ์๋ค.
- Quick Sort ๊ณผ์ ์ ๋ํด ์ค๋ช ํ ์ ์๋ค.
- Quick Sort์ ๊ตฌํํ ์ ์๋ค.
- Quick Sort์ ์๊ฐ๋ณต์ก๋์ ๊ณต๊ฐ๋ณต์ก๋๋ฅผ ๊ณ์ฐํ ์ ์๋ค.
- Quick Sort์ ์ต์ ์ธ ๊ฒฝ์ฐ๋ฅผ ๊ฐ์ ์ํฌ ์ ์๋ค.
# Abstract
Quick Sort์ ๋ถํ ์ ๋ณต(divide and conquer) ๋ฐฉ๋ฒ ์ ํตํด ์ฃผ์ด์ง ๋ฐฐ์ด์ ์ ๋ ฌํ๋ค.
* [๋ถํ ์ ๋ณต(divide and conquer) ๋ฐฉ๋ฒ]
๋ฌธ์ ๋ฅผ ์์ 2๊ฐ์ ๋ฌธ์ ๋ก ๋ถ๋ฆฌํ๊ณ ๊ฐ๊ฐ์ ํด๊ฒฐํ ๋ค์, ๊ฒฐ๊ณผ๋ฅผ ๋ชจ์์ ์๋์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ์ ๋ต์ด๋ค.
Quick Sort์ ๋ถ์์ ์ ๋ ฌ์ ์ํ๋ฉฐ, ๋ค๋ฅธ ์์์์ ๋น๊ต๋ง์ผ๋ก ์ ๋ ฌ์ ์ํํ๋ ๋น๊ต ์ ๋ ฌ์ ์ํ๋ค. ๋ํ Merge Sort์ ๋ฌ๋ฆฌ Quick Sort๋ ๋ฐฐ์ด์ ๋น๊ท ๋ฑํ๊ฒ ๋ถํ ํ๋ค.
# Process (Ascending)
- ๋ฐฐ์ด ๊ฐ์ด๋ฐ์ ํ๋์ ์์๋ฅผ ๊ณ ๋ฅธ๋ค. ์ด๋ ๊ฒ ๊ณ ๋ฅธ ์์๋ฅผ ํผ๋ฒ(pivot) ์ด๋ผ๊ณ ํ๋ค.
- ํผ๋ฒ ์์๋ ํผ๋ฒ๋ณด๋ค ๊ฐ์ด ์์ ๋ชจ๋ ์์๋ค์ด ์ค๊ณ , ํผ๋ฒ ๋ค์๋ ํผ๋ฒ๋ณด๋ค ๊ฐ์ด ํฐ ๋ชจ๋ ์์๋ค์ด ์ค๋๋ก ํผ๋ฒ์ ๊ธฐ์ค์ผ๋ก ๋ฐฐ์ด์ ๋๋ก ๋๋๋ค. ์ด๋ ๊ฒ ๋ฐฐ์ด์ ๋๋ก ๋๋๋ ๊ฒ์ ๋ถํ (Divide) ์ด๋ผ๊ณ ํ๋ค. ๋ถํ ์ ๋ง์น ๋ค์ ํผ๋ฒ์ ๋ ์ด์ ์์ง์ด์ง ์๋๋ค.
- ๋ถํ ๋ ๋ ๊ฐ์ ์์ ๋ฐฐ์ด์ ๋ํด ์ฌ๊ท(Recursion)์ ์ผ๋ก ์ด ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
- ์ฌ๊ท ํธ์ถ์ด ํ๋ฒ ์งํ๋ ๋๋ง๋ค ์ต์ํ ํ๋์ ์์๋ ์ต์ข ์ ์ผ๋ก ์์น๊ฐ ์ ํด์ง๋ฏ๋ก, ์ด ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ๋์ ๋๋๋ค๋ ๊ฒ์ ๋ณด์ฅํ ์ ์๋ค.
# Java Code (Ascending)
ํต ์ ๋ ฌ์ ๋ค์์ ๋จ๊ณ๋ค๋ก ์ด๋ฃจ์ด์ง๋ค.
์ ๋ณต (Conquer)
๋ถ๋ถ ๋ฐฐ์ด์ ์ ๋ ฌํ๋ค. ๋ถ๋ถ ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ ์ถฉ๋ถํ ์์ง ์์ผ๋ฉด ์ํ ํธ์ถ์ ์ด์ฉํ์ฌ ๋ค์ ๋ถํ ์ ๋ณต ๋ฐฉ๋ฒ์ ์ ์ฉํ๋ค.
public void quickSort(int[] array, int left, int right) { if(left >= right) return; // ๋ถํ int pivot = partition(); // ํผ๋ฒ์ ์ ์ธํ 2๊ฐ์ ๋ถ๋ถ ๋ฐฐ์ด์ ๋์์ผ๋ก ์ํ ํธ์ถ quickSort(array, left, pivot-1); // ์ ๋ณต(Conquer) quickSort(array, pivot+1, right); // ์ ๋ณต(Conquer) }
๋ถํ (Divide)
์ ๋ ฅ ๋ฐฐ์ด์ ํผ๋ฒ์ ๊ธฐ์ค์ผ๋ก ๋น๊ท ๋ฑํ๊ฒ 2๊ฐ์ ๋ถ๋ถ ๋ฐฐ์ด (ํผ๋ฒ์ ์ค์ฌ์ผ๋ก ์ผ์ชฝ : ํผ๋ฒ๋ณด๋ค ์์ ์์๋ค, ์ค๋ฅธ์ชฝ : ํผ๋ฒ๋ณด๋ค ํฐ ์์๋ค) ๋ก ๋ถํ ํ๋ค.
public int partition(int[] array, int left, int right) { /** // ์ต์ ์ ๊ฒฝ์ฐ, ๊ฐ์ ๋ฐฉ๋ฒ int mid = (left + right) / 2; swap(array, left, mid); */ int pivot = array[left]; // ๊ฐ์ฅ ์ผ์ชฝ๊ฐ์ ํผ๋ฒ์ผ๋ก ์ค์ int i = left, j = right; while(i < j) { while(pivot < array[j]) { j--; } while(i < j && pivot >= array[i]){ i++; } swap(array, i, j); } array[left] = array[i]; array[i] = pivot; return i; }
# Quick Sort ๊ฐ์
partition() ํจ์์์ ํผ๋ฒ ๊ฐ์ด ์ต์๋ ์ต๋๊ฐ์ผ๋ก ์ง์ ๋์ด ํํฐ์ ์ด ๋๋์ด์ง์ง ์์์ ๋, O(n^2)์ ๋ํ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
์ฆ, ์ ๋ ฌํ๊ณ ์ ํ๋ ๋ฐฐ์ด์ด ์ค๋ฆ์ฐจ์ ์ ๋ ฌ๋์ด์๊ฑฐ๋ ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ๋์ด์์ผ๋ฉด O(n^2)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค. ์ด๋, ๋ฐฐ์ด์์ ๊ฐ์ฅ ์์ ์๋ ๊ฐ๊ณผ ์ค๊ฐ๊ฐ์ ๊ตํํด์ค๋ค๋ฉด ํ๋ฅ ์ ์ผ๋ก๋๋ง ์๊ฐ๋ณต์ก๋ O(nlogโn)์ผ๋ก ๊ฐ์ ํ ์ ์๋ค. ํ์ง๋ง, ์ด ๋ฐฉ๋ฒ์ผ๋ก ๊ฐ์ ํ๋คํด๋ Quick Sort์ ์ต์
์ ์๊ฐ๋ณต์ก๋๊ฐ O(nlogโn)๊ฐ ๋๋ ๊ฒ์ ์๋๋ค.
# GIF๋ก ์ดํดํ๋ Quick Sort
# ์๊ฐ๋ณต์ก๋
# ์ต์ ์ ๊ฒฝ์ฐ(Best cases) : T(n) = O(nlogโn)
๋น๊ต ํ์
(logโn)
๋ ์ฝ๋์ ๊ฐ์ n์ด 2์ ๊ฑฐ๋ญ์ ๊ณฑ์ด๋ผ๊ณ ๊ฐ์ (n=2^k) ํ์ ๋, n=2^3์ ๊ฒฝ์ฐ, 2^3 -> 2^2 -> 2^1 -> 2^0 ์์ผ๋ก ์ค์ด๋ค์ด ์ํ ํธ์ถ์ ๊น์ด๊ฐ 3์์ ์ ์ ์๋ค.
์ด๊ฒ์ ์ผ๋ฐํํ๋ฉด n=2^k์ ๊ฒฝ์ฐ, k(k=logโn) ์์ ์ ์ ์๋ค.
๊ฐ ์ํ ํธ์ถ ๋จ๊ณ์ ๋น๊ต ์ฐ์ฐ
(n)
๊ฐ ์ํ ํธ์ถ์์๋ ์ ์ฒด ๋ฆฌ์คํธ์ ๋๋ถ๋ถ์ ๋ ์ฝ๋๋ฅผ ๋น๊ตํด์ผ ํ๋ฏ๋ก ํ๊ท n๋ฒ ์ ๋์ ๋น๊ต๊ฐ ์ด๋ฃจ์ด์ง๋ค.
๋ฐ๋ผ์, ์ต์ ์ ์๊ฐ๋ณต์ก๋๋ ์ํ ํธ์ถ์ ๊น์ด * ๊ฐ ์ํ ํธ์ถ ๋จ๊ณ์ ๋น๊ต ์ฐ์ฐ = nlogโn
๊ฐ ๋๋ค. ์ด๋ ํ์๋ ๋น๊ต ํ์๋ณด๋ค ์ ์ผ๋ฏ๋ก ๋ฌด์ํ ์ ์๋ค.
# ์ต์ ์ ๊ฒฝ์ฐ(Worst cases) : T(n) = O(n^2)
์ต์ ์ ๊ฒฝ์ฐ๋ ์ ๋ ฌํ๊ณ ์ ํ๋ ๋ฐฐ์ด์ด ์ค๋ฆ์ฐจ์ ์ ๋ ฌ๋์ด์๊ฑฐ๋ ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ๋์ด์๋ ๊ฒฝ์ฐ๋ค.
๋น๊ต ํ์
(n)
๋ ์ฝ๋์ ๊ฐ์ n์ด 2์ ๊ฑฐ๋ญ์ ๊ณฑ์ด๋ผ๊ณ ๊ฐ์ (n=2^k)ํ์ ๋, ์ํ ํธ์ถ์ ๊น์ด๋ n ์์ ์ ์ ์๋ค.
๊ฐ ์ํ ํธ์ถ ๋จ๊ณ์ ๋น๊ต ์ฐ์ฐ
(n)
๊ฐ ์ํ ํธ์ถ์์๋ ์ ์ฒด ๋ฆฌ์คํธ์ ๋๋ถ๋ถ์ ๋ ์ฝ๋๋ฅผ ๋น๊ตํด์ผ ํ๋ฏ๋ก **ํ๊ท n๋ฒ ** ์ ๋์ ๋น๊ต๊ฐ ์ด๋ฃจ์ด์ง๋ค.
๋ฐ๋ผ์, ์ต์
์ ์๊ฐ๋ณต์ก๋๋ ์ํ ํธ์ถ์ ๊น์ด * ๊ฐ ์ํ ํธ์ถ ๋จ๊ณ์ ๋น๊ต ์ฐ์ฐ = n^2
๋ค. ์ด๋ ํ์๋ ๋น๊ต ํ์๋ณด๋ค ์ ์ผ๋ฏ๋ก ๋ฌด์ํ ์ ์๋ค.
# ํ๊ท ์ ๊ฒฝ์ฐ(Average cases) : T(n) = O(nlogโn)
# ๊ณต๊ฐ๋ณต์ก๋
์ฃผ์ด์ง ๋ฐฐ์ด ์์์ ๊ตํ(swap)์ ํตํด, ์ ๋ ฌ์ด ์ํ๋๋ฏ๋ก **O(n)**์ด๋ค.
# ์ฅ์
- ๋ถํ์ํ ๋ฐ์ดํฐ์ ์ด๋์ ์ค์ด๊ณ ๋จผ ๊ฑฐ๋ฆฌ์ ๋ฐ์ดํฐ๋ฅผ ๊ตํํ ๋ฟ๋ง ์๋๋ผ, ํ ๋ฒ ๊ฒฐ์ ๋ ํผ๋ฒ๋ค์ด ์ถํ ์ฐ์ฐ์์ ์ ์ธ๋๋ ํน์ฑ ๋๋ฌธ์, ์๊ฐ ๋ณต์ก๋๊ฐ O(nlogโn)๋ฅผ ๊ฐ์ง๋ ๋ค๋ฅธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋น๊ตํ์ ๋๋ ๊ฐ์ฅ ๋น ๋ฅด๋ค.
- ์ ๋ ฌํ๊ณ ์ ํ๋ ๋ฐฐ์ด ์์์ ๊ตํํ๋ ๋ฐฉ์์ด๋ฏ๋ก, ๋ค๋ฅธ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ํ์๋ก ํ์ง ์๋๋ค.
# ๋จ์
- ๋ถ์์ ์ ๋ ฌ(Unstable Sort) ์ด๋ค.
- ์ ๋ ฌ๋ ๋ฐฐ์ด์ ๋ํด์๋ Quick Sort์ ๋ถ๊ท ํ ๋ถํ ์ ์ํด ์คํ๋ ค ์ํ์๊ฐ์ด ๋ ๋ง์ด ๊ฑธ๋ฆฐ๋ค.
# Conclusion
ํ๊ท ์ ์ผ๋ก ๊ฐ์ฅ ๋น ๋ฅธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋ํด์ ์์๋ดค๋ค. JAVA์์ Arrays.sort() ๋ด๋ถ์ ์ผ๋ก๋ Dual Pivot Quick Sort๋ก ๊ตฌํ๋์ด ์์ ์ ๋๋ก ํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ด๊ณ , ๊ธฐ์ ๋ฉด์ ์์ ์ ๋ง ๋น๋ฒํ๊ฒ ๋์ค๋ ์ฃผ์ ์ด๋ฏ๋ก ๋ฐ๋์ ์์งํ์